/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-19
 * Time: 19:03
 */
public class TestDemo  {

    //机器人从start位置开始走K步,目的地是aim,总共有1~N这样的位置
    //求机器人总共到达目的地有几种走法
    public static int ways1(int start,int k,int aim,int N){

        return process(start,k,aim,N);
    }

//    cur代表机器人当前的位置
//    rest代表机器人剩下的步数
//    aim是目的地
//    N总共有N步
    public static int process(int cur,int rest,int aim,int N) {
        if(rest==0){
            //机器人没有剩下的步数了,不能在走了
            //如果cur的位置正好在aim位置,那说明走法为1,否则为0
            return aim == cur ? 1 : 0;
        }
        //特殊条件
        if(cur==1){
            //如果cur在坐左边的位置,也就是起始位置,那说明,不能往左走,只能往右走
            //它的总共走法就等于在cur+1的位置上,走rest-1步
            return process(2,rest-1,aim,N);
        }
        if(cur==N){
            //如果cur在最右边的位置,也就是最后的一个位置,那说明,不能往右走,只能往左走
            //它的总共走法就是,当前位置在cur-1,还能走rest-1步
            return process(N-1,rest-1,aim,N);
        }
        //如果在中间位置,那说明既可以往左走又可以往右走
        return process(cur-1,rest-1,aim,N)+
                process(cur+1,rest-1,aim,N);
    }

    public static int ways2(int start,int k,int aim,int N){
        //可变参数为 start K
        //start的范围为 1~N
        //K的范围为1~K
        int[][] dp = new int[N+1][k+1];
        for(int i =0;i<=N;i++){
            for(int j =0;j<=k;j++){
                dp[i][j] = -1;
            }
        }
        return process1(start,k,aim,N,dp);
    }

    public static int process1(int cur,int rest,int aim,int N,int[][] dp){
        if(dp[cur][rest]!=-1){
            return dp[cur][rest];
        }
        int ans = 0;
        if(rest==0){
            ans = cur==aim ? 1:0;
        } else if(cur==1){
            ans =  process1(2,rest-1,aim,N,dp);
        }else if(cur==N){
            ans =  process1(N-1,rest-1,aim,N,dp);
        } else {
            ans = process1(cur+1,rest-1,aim,N,dp)
                    +process1(cur-1,rest-1,aim,N,dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }

    public static int ways3(int start,int k,int aim,int N){
        int[][] dp = new int[N+1][k+1];
        dp[aim][0] = 1;//没有剩余步数的时候,只有在目标位置时次数为1,否则为0
        for(int rest = 1;rest<=k;++rest){
            dp[1][rest] = dp[2][rest-1];
            for(int cur = 2;cur<N;++cur){
                dp[cur][rest] = dp[cur-1][rest-1] +dp[cur+1][rest-1];
            }
            dp[N][rest] = dp[N-1][rest-1];
        }
        return dp[start][k];
    }

    public static void main(String[] args) {
       System.out.println(ways1(2, 4, 4, 4));
        System.out.println(ways2(2, 4, 4, 4));
        System.out.println(ways3(2, 4, 4, 4));

    }


}
